/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package huffmancompression;

import java.util.LinkedList;

/**
 *
 * @author Agustin
 */
public class Huffman {
    
    public int contador, contadorBitsHuffman;
            
    public Huffman(){
    }
    
    public void Iniciar(String input){
        LinkedList<String> Caracteres = new LinkedList<String>();
        LinkedList<Integer> Frecuencias = Frecuencia(input, Caracteres);
        LinkedList<NodoContadorBits> contadorBits = new LinkedList<NodoContadorBits>();
        QuickSort qS = new QuickSort();
        qS.Sort(Frecuencias, Caracteres);
        
        for(int i = 0; i < Caracteres.size(); i++){
            System.out.print(Caracteres.get(i));
            System.out.print(Frecuencias.get(i));
            System.out.println();
        }
        
        Nodo n = this.Huffman(Frecuencias, Caracteres);
        contador = 0;
        this.Imprimir(n, 0, contadorBits, 0);
        System.out.println();
        System.out.println("Huffman");
        System.out.print(this.CalcularBitsHuffman(input, contadorBits));
        System.out.println(" bits");
        System.out.println(contador);
        
        System.out.println();
        System.out.println("Normal");
        System.out.print(this.CalcularBitsNormal(input, contador));
        System.out.println(" bits");
        System.out.println(this.CalculoArbolCompleto(Frecuencias.size()));
        // Buscar
        /*
        int encontrado = this.Buscar('b', Frecuencias, Caracteres);
        
        if(encontrado > -1){
            this.Imprimir(n, encontrado);
        }
        else{
            System.out.print("Nada!!!...");
        }
        */    
    }
    
    private int CalculoArbolCompleto(int noHojas){
        int noNodos = noHojas;
        double prueba = 0.0, actual = noHojas;
        
        //int altura = (int) Math.floor(Math.log10(noHojas)/Math.log10(2));
        //hojas = (int) ((Math.pow(2, altura + 0.0) - 1) + (noHojas - (Math.pow(2, altura + 0.0) - noHojas)));
        
        while(actual > 1){
            prueba = actual / 2.0;
            actual = Math.ceil(prueba);
            noNodos += actual;
        }
        
        return noNodos;
    }
    
    private void Imprimir(Nodo n, int Encontrado, LinkedList<NodoContadorBits> contadorBits, int altura){
        
        if(n != null)
        {
            if(n.HijoDerecho == null && n.HijoIzquierdo == null){
                NodoContadorBits nodoContadorBits = new NodoContadorBits();
                nodoContadorBits.Caracter = n.Caracter;
                nodoContadorBits.noBits = altura;
                
                contadorBits.add(nodoContadorBits);
            }
            
            altura++;
            contador++;
            
            //System.out.print("Nodo, ");
            this.Imprimir(n.HijoIzquierdo, Encontrado, contadorBits, altura);
            this.Imprimir(n.HijoDerecho, Encontrado, contadorBits, altura); 
        }
    }
    
    private int CalcularBitsNormal(String cadenaEntrada, int noHojas){
        int noBits = (int) Math.floor(Math.log10(noHojas)/Math.log10(2));
        
        return cadenaEntrada.length() * noBits;
    }
    
    private int CalcularBitsHuffman(String cadenaEntrada, LinkedList<NodoContadorBits> contadorBits){
        int noBits = 0;
        
        for(int i = 0; i < cadenaEntrada.length(); i++){
            for(int j = 0; j < contadorBits.size(); j++){
                if(Character.toString(cadenaEntrada.charAt(i)).equals(contadorBits.get(j).Caracter)){
                    noBits += contadorBits.get(j).noBits;
                }
            }
        }
        
        return noBits;
    }
    
    private int Buscar(char caracter, LinkedList<Integer> F, 
            LinkedList<String> C){
        
        int temp = -1;
        
        if(C.contains(Character.toString(caracter)))
        {
            temp = F.get(C.indexOf(Character.toString(caracter)));
        }
        
        return temp;
    }
    
    private LinkedList<Integer> Frecuencia(String input, LinkedList<String> Caracteres){
        LinkedList<Integer> Frecuencias = new LinkedList<Integer>();
        Integer temp = 0;
        
        for(int i = 0; i < input.length(); i++)
        {
            if(Caracteres.contains(Character.toString(input.charAt(i))))
            {
                temp = Frecuencias.get(Caracteres.indexOf(Character.toString(input.charAt(i))));
                temp++;
                Frecuencias.set(Caracteres.indexOf(Character.toString(input.charAt(i))), temp);
            }
            else
            {
                Caracteres.add(Character.toString(input.charAt(i)));
                Frecuencias.add(1);
            }
        }
        
        return Frecuencias;
    }
    
    private Nodo Huffman(LinkedList<Integer> F, LinkedList<String> C)
    {
        int n = C.size();
        LinkedList<Nodo> Q = new LinkedList<Nodo>();
        
        for(int i = 0; i < n; i++)
        {
            Nodo nod = new Nodo();
            nod.Caracter = C.get(i);
            nod.Frecuencia = F.get(i);
                    
            Q.add(nod);
        }
        
        for(int i = 0; i < n - 1; i++)
        {
            Nodo z = new Nodo();
            Nodo x = this.ExtractMin(Q);
            Nodo y = this.ExtractMin(Q);
            
            z.HijoIzquierdo = x;
            z.HijoDerecho = y;
            z.Frecuencia = x.Frecuencia + y.Frecuencia;
            z.Caracter = "";
            
            this.Insert(Q, z);
        }
        
        return this.ExtractMin(Q);
    }
    
    private Nodo ExtractMin(LinkedList<Nodo> Q){
        Nodo t = Q.get(0);
        
        Q.remove(0);
        
        return t;
    }
    
    private void Insert(LinkedList<Nodo> Q, Nodo n){
        
        boolean b = true;
        
        for(int i = 0; i < Q.size(); i++)
        {
            if(Q.get(i).Frecuencia >= n.Frecuencia){
                Q.add(i, n);
                b = false;
                break;
            }
        }
        
        if(b){
            Q.add(0, n);
        }
    }
}